package com.leecode;

public class Leet73 {
	public static void main(String[] args) {
//		new Leet73().minDistance("intention", "execution");
		new Leet73().minDistance("horse", "ros");
	}

	public int minDistance(String word1, String word2) {
		if (word1.length() >= word2.length()) {
			return minD(word1, word2);
		} else {
			return minD(word2, word1);
		}
	}

	public int minD(String longS, String shorS) {
		char[] longA = longS.toCharArray();
		char[] shorA = shorS.toCharArray();
		int[] res = new int[shorA.length];
		for (int a = 0; a < res.length; a++) {
			res[a] = -1;
		}

		int temp = 0;
		int pre = 0;
		h:
		for (int s = 0; s < shorA.length; s++) {
			for (int l = temp; l < longA.length; l++) {
				if (longA[l] == shorA[s]) {
					if (l == temp) {
						res[pre] = -1;//restore
					}
					temp = l;
					pre = s;
					res[s] = l;
					continue h;
				}
			}
		}

		int sum = 0;
		for (int c = 0; c < res.length; c++) {
			if (res[c] == -1) {
				sum += 1;
			}
		}

		for (int d = 0; d < res.length - 1; d++) {
			if (res[d] != -1) {
				for (int e = d + 1; e < res.length; e++) {
					if (res[e] != -1) {
						if (res[e] - res[d] - (e - d) > 0) {
							sum += res[e] - res[d] - (e - d);
						}
						d = e;
						break;
					}
				}
			}
		}

		int bb=0;
		while (res[bb] == -1) {
			bb++;
		}
		if(res[bb]-bb>0){
			sum+=res[bb]-bb;
		}
		int ee=res.length-1;
		while(res[ee]==-1){
			ee--;
		}
		if(longA.length-1-ee>0){
			sum+=longA.length-1-ee;
		}

		return sum;
	}
}
